#include<vector>
#include<iostream>
using std::vector;



class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 找到旋转点
        int k = this->findRotation(nums);

        //if (k == -1) k = left+1;
        std::cout << "k: " << k << "\n";
        // 找到选择点后，正常搜索就行 [0, k)
        int pos = this->binarySearch(nums, 0, k, target);
        if (pos != -1) return pos;
        // [k, N)
        else return this->binarySearch(nums, k, nums.size(), target);
    }

    int binarySearch(vector<int>& nums, int left, int right, int target) {
        // 简单的二分搜索
        while (left < right) {
            auto mid = (left + right) / 2;
            std::cout << "(" << left << ", " << mid << ", " << right << ")" << " mid is : " << nums[mid] << "\n";
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid+1;
            else right = mid;
        }
        return -1;
    }

    int findRotation(vector<int>& nums) {
        int left = 0, right = nums.size();
        if (nums[left] <= nums[right-1]) return 0;  //非rotation
        while (left < right) {
            if (right - left < 3) { //数组小直接遍历
                for (auto i = left; i < right-1; i++) {
                    if (nums[i] > nums[i+1]) return i+1;
                    return left;
                }
            }
            auto mid = (left + right) / 2;
            if (nums[mid] < nums[left]) right = mid + 1;
            else left = mid;
        }
        return -1;
    }
};



int main() {
    vector<int> input = {};
    int n;
    while (std::cin >> n) {
        input.push_back(n);
    }
    std::cout << "input: \n";
    for (auto k: input) std::cout << k << " ";
    std::cout << "\n";
    

    auto res = Solution().search(input, 0);
    std::cout << res;
    return 0;
}